package com.south.base.test.arithmetic.arrays;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

import static com.south.base.test.arithmetic.IntegerOperation.gcd;

/**
 * @author Administrator
 * @date 2020/7/30 11:14
 */
public class Split {
    /**
     * 切分数组
     * 给定一个整数数组 nums ，小李想将 nums 切割成若干个非空子数组，
     * 使得每个子数组最左边的数和最右边的数的最大公约数大于 1 。
     * 请求出最少可以切成多少个子数组。
     */
    @Test
    public void splitArray() {
        Assert.assertEquals(2, splitArray(new int[]{2, 3, 3, 2, 3, 3}));
        Assert.assertEquals(4, splitArray(new int[]{2, 3, 5, 7}));
        Assert.assertEquals(2, splitArray2(new int[]{2, 3, 3, 2, 3, 3}));
        Assert.assertEquals(4, splitArray2(new int[]{2, 3, 5, 7}));
    }

    public int splitArray(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[nums.length - 1] = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            for (int j = nums.length - 1; j > i; j--) {
                int gcd = gcd(nums[j], nums[i]);
                if (gcd > 1) {
                    dp[i] = Math.min(dp[i], dp[j]);
                }
            }
            if (dp[i] == Integer.MAX_VALUE || dp[i] > dp[i + 1] + 1) {
                dp[i] = dp[i + 1] + 1;
            }
        }
        return dp[0];
    }

    public int splitArray2(int[] nums) {
        // 通过这种标记的方式 能够在O(1)的时间内找到自己的公约数
        int[] tmp = new int[1000000 + 1];
        for (int i = 2; i < tmp.length; i++) {
            if (tmp[i] == 0)
                for (int j = i; j < tmp.length; j += i)
                    tmp[j] = i;
        }
        // 保存每个公约数的最小分组结果
        Map<Integer, Integer> map = new HashMap<>();
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            res[i] = i > 0 ? res[i - 1] + 1 : 1;
            int cur = nums[i];
            while (cur > 1) {
                int divisor = tmp[cur];
                int minSit = map.getOrDefault(divisor, -1);
                if (minSit == -1)
                    map.put(divisor, i);
                else if (minSit == 0)
                    res[i] = 1;
                else {
                    res[i] = Math.min(res[i], res[minSit - 1] + 1);
                    // 更新公约数的最小分组结果
                    if (res[i - 1] < res[minSit - 1])
                        map.put(divisor, i);
                }
                cur = cur / divisor;
            }
        }
        return res[nums.length - 1];
    }
}
